package com.leetcode.leetcode3;

/**
 * 颜色分类
 * 给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
 *
 * @author luhd
 * @date 2024-04-26
 */
public class Practice75 {

    /**
     * 示例 1：
     *
     * 输入：nums = [2,0,2,1,1,0]
     * 输出：[0,0,1,1,2,2]
     * 示例 2：
     *
     * 输入：nums = [2,0,1]
     * 输出：[0,1,2]
     */
    public static void main(String[] args) {
        int[] nums = {2,0,2,1,1,0};
        sortColors(nums);
        for (int i = 0; i < nums.length; i++) {
            System.out.print(nums[i]);
        }
    }

    public static void sortColors(int[] nums) {
        // for (int i = 0; i < nums.length; i++) {
        //     for (int j = i+1; j < nums.length; j++) {
        //         if (nums[i]>nums[j]) {
        //             swap(nums, i, j);
        //         }
        //     }
        // }
        int len = nums.length;
        for (int i = 1; i < len; i++) {  //因为arr[0]相当于已排序序列，所以从arr[1]开始
            int index = i-1;  //即当前数组下标和前面的数组下标相比较
            int current = nums[i];  //当前未排序序列的第一个值，即待插入数值
            while(index >=0 && nums[index]>current){  //确保数组下标符合条件，其次当未排序序列的第一个值，比前一个值小的时候，应该移位
                nums[index +1] = nums[index];   //将(当未排序序列的第一个值)的前一个值向后移一位
                index --; //当前的数组下标递减，类似于指针向前移位，判断(当未排序序列的第一个值)与前第二位的数值的比较
            }
            nums[index+1] = current;   //最后将待插入数值 插入到合适的位置,前面的index--,所以此处应该+1
        }
    }

    /**
     *  交换数组中两个元素的位置
     */
    public static void swap(int[] arr ,int i ,int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}